#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <vector>
#include <iostream>
using namespace std;
namespace Lnb
{
	enum State
	{
		DELETE,
		EMPTY,
		EXIST
	};
	template<class K, class V>
	struct HashData
	{
		State _state = EMPTY;
		pair<K, V> _kv;
	};

template<class K,class V>
class HashTable
{
public:
	HashData<K,V>* Find(const K& key)
	{
		if (_table.size() == 0)
		{
			return nullptr;
		}
		int hash = key% _table.size();
		int index = hash;
		int i = 1;
		while (_table[index]._state != EMPTY)
		{
			if (_table[index]._state == EXIST && (_table[index]._kv.first == key))
			{
				return &_table[index];
			}
			index = hash + i;
			i++;
			index %= _table.size();
		}
		return nullptr;


	}




	bool insert(const pair<K, V>& kv)
	{
		if (Find(kv.first))
		{
			return false;
		}
		if (!(_table.size()) || (_n * 10 / _table.size() >= 7))
		{
			HashTable h;
			int newsize = _table.size() == 0 ? 10 : _table.size() * 2;
			h._table.resize(newsize);
			for (auto data : _table)
			{
				if (data._state == EXIST)
				{
					h.insert(data._kv);
				}
			}
			_table.swap(h._table);
		}
		int i = 1;
		int hash = kv.first%_table.size();
		int index = hash;
		while (_table[index]._state == EXIST)
		{
			index=hash+i;
			i++;
			index %= _table.size();
		}

		_table[index]._kv = kv;
		_table[index]._state = EXIST;
		_n++;
		return true;
	}

	bool Erase(const K& k)
	{
		auto ret = Find(k);
		if (ret == nullptr)
		{
			return false;
		}
		else
		{
			ret->_state = DELETE;
			_n--;
			return true;
		}

	}







private:
	vector<HashData<K, V>> _table;
	int _n = 0;

};



void Test()
{
	int arr[] = { 2,3,33,13,5,12,1002 };
	HashTable<int, int> h;
	for (auto e : arr)
	{
		h.insert(make_pair(e, e));
	}
	h.insert(make_pair(15, 15));

}







}